package interview.questions.缺少的数字;

/**
 * 问题：
 * <p>
 * 在包含1~100的数组中，查找任意丢失的一个数字
 */
public class Solution {

    /**
     * 思路：1. 算出1~100的和sum.
     * 2. 计算出给定数组所有数之和otherSum.
     * 3. 丢失的数字为sum-otherSum.
     */
    public static int findMissingNumber(int[] nums) {
        int n = nums.length;

        int sum = (100 + 1) * 100 / 2;

        int otherSum = 0;

        for (int i : nums) {

            otherSum += i;

        }

        return sum - otherSum;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 4, 5, 6,  8, 9, 10,
                11, 12, 13, 14, 15, 16,17, 18, 19, 20,
                21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
                41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
                51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
                61, 62, 63, 64,65, 66, 67, 68, 69, 70,
                71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
                81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
                91, 92, 93, 94, 95, 96,97, 98, 99, 100 };

        System.out.println(findMissingNumber(nums));

    }
}
